# Copyright 2007 Boris Dusek
#
# This file is part of grapy.
#
# Grapy is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, version 3 of the License.
#
# Grapy is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with Grapy.  If not, see <http://www.gnu.org/licenses/>.

import sys

from grapy.AdjListGraph import AdjListGraph
from grapy.Graph import Graph, graph_option_parser
from grapy.DFSHooks import *

if __name__ == "__main__":
    parser = graph_option_parser()

    parser.add_option("-b", "--bridges", action="store_true", dest="bridges",
            default=False, help="Print bridges (only for undirected graphs)")
    
    parser.add_option("-a", "--articulations", action="store_true",
            dest="articulations",default=False,
            help="Print articulations (only for undirected graphs)")

    parser.add_option("-n", "--no-components", action="store_false",
            dest="components", default=True,
            help="Compute components for undirected graphs")

    parser.add_option("-t", "--topological-sort", action="store_true",
            dest="topological_sort", default=False,
            help="Topologically sorts the vertices (undirected graphs only)")

    parser.add_option("-s", "--scc", "--strongly-connected-components",
            action="store_true", dest="scc", default=False,
            help="Computes strongly connected components")

    parser.add_option("-o", "--sorted", "--ordered",
            action="store_true", dest="sorted", default=False,
            help="Iterates over the vertices in sorted manner.")

    (options,args) = parser.parse_args()

    g = AdjListGraph(options.multi,options.directed)
    f = open(args[0],"r")
    g.init_from_stream(f)
    f.close()

    additional_hooks = [PredecessorDFSHooks]
    options.components = options.components and not options.directed
    if options.components:
        additional_hooks.append(ComponentsDFSHooks)
    if options.topological_sort:
        from grapy.TopologicalSort import TopologicalSortDFSHooks
        additional_hooks.append(TopologicalSortDFSHooks)
    if options.sorted:
        additional_hooks.append(SortedDFSHooks)
    dfs_hooks = DFSHooksSuite(additional_hooks)
    dfs_hooks.resolve_deps()
    dfs_environ = g.DFS(dfs_hooks)

    if options.scc:
        from grapy.StronglyConnectedComponents import \
                strongly_connected_components
        scc = strongly_connected_components(g,dfs_environ)

    d,f,p = dfs_environ.d, dfs_environ.f, dfs_environ.p

    length = max([len(s) for s in g.vertices()])
    fmt_string = "%*s: %3d %3d   %*s"
    header = "%*sv    d   f   %*sp" % ((length-1), "", (length-1), "")
    if options.articulations or options.bridges:
        low,b,ch = g.compute_bicon_info(d,p)

        if options.articulations:
            #low = dfs_environ.low
            #ch = dfs_environ.ch
            articulations = Graph.articulations(d,p,low,ch)
        if options.bridges:
            #b = dfs_environ.b
            bridges       = Graph.bridges      (d,p,b  ,ch)

        if options.articulations:
            header += " low"
            fmt_string += " %3d"
        if options.bridges:
            header += "   b"
            fmt_string += " %3d"
        if options.articulations:
            header += "  ch"
            fmt_string += " %3d"        

    if options.components:
        cc = dfs_environ.component
        header += " com"
        fmt_string += " %3d"

    if options.scc:
        header += " scc"
        fmt_string += " %3d"

    print header
    for v in g.vertices():
        if p[v] is not None:
            pp = p[v]
        else:
            pp = "N"
        fmt_args = [length,v,d[v],f[v],length,pp]
        if options.articulations:
            fmt_args.append(low[v])
        if options.bridges:
            fmt_args.append(b[v])
        if options.articulations:
            fmt_args.append(len(ch[v]))
        if options.components:
            fmt_args.append(cc[v])
        if options.scc:
            fmt_args.append(scc[v])
        print fmt_string % tuple(fmt_args)

    if options.articulations:
        print "Articulations: ", [u for u in articulations]
    if options.bridges:
        print "Bridges: ", [(e[0],e[1]) for e in bridges]
    if options.topological_sort:
        print "Topological order: ", dfs_environ.topological_order
